package reviewAlgorithms.tree;

public class LowestCommonAncestor {
    public static void main(String[] args) {

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return root;
        }
        int h = p.val;
        int l = q.val;
        if (p.val < q.val){
            h = q.val;
            l = p.val;
        }
        return lowestCommonAncestor(root,l,h);
    }

    private TreeNode lowestCommonAncestor(TreeNode root, int l, int h) {
        if (root == null){
            return null;
        }
        if (root.val <= h && root.val >= l){
            return root;
        }
        if (root.val < l){
            return lowestCommonAncestor(root.right,l,h);
        }else {
            return lowestCommonAncestor(root.left,l,h);
        }
    }
}
